package leetcode.editor.cn.q1_300.q250;
//给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。 
//
// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
// 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：3 
//解释：12 = 4 + 4 + 4 
//
// 示例 2： 
//
// 
//输入：n = 13
//输出：2
//解释：13 = 4 + 9 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁴ 
// 
//
// 👍 1738 👎 0

/**
 * 找到距离 n 最近的完全平方数 m，然后再找到和 n-m 距离最近的数。。。。
 * 直到 n 为 0，统计完全平方数的个数
 * <p>
 * 上面的思路是错误的，比如 18，最低应该是 2 个 9，如果按照上面的逻辑得到的结果是 16+1+1 3个数
 * <p>
 * 动态规划：
 * 对于 n 来说，都是由比 n 小的数相加得到的，n = (n-i) + i，
 * 建立数组arr[n]，每个下标 i，代表了 i 是由几个完全平方数组成的，那么 n 就是 min(arr[n-i]+arr[i])
 */
public class Q279_PerfectSquares {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numSquares(int n) {
            int[] arr = new int[n + 1];
            for (int i = 1; i <= 100; i++) {
                int square = i * i;
                if (square > n) {
                    break;
                }
                arr[square] = 1;
            }

            for (int i = 2; i <= n; i++) {
                int min = 100;
                if (arr[i] != 0) {
                    continue;
                }
                for (int j = 1; j < i; j++) {
                    min = Math.min(min, arr[j] + arr[i - j]);
                }
                arr[i] = min;
            }

            return arr[n];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q279_PerfectSquares().new Solution();
        System.out.println(solution.numSquares(18));
        ;
        System.out.println(solution.numSquares(48));
        ;
        // TO TEST
        for (int i = 1; i <= 20; i++) {
            System.out.println(i + "\t" + solution.numSquares(i));
        }
    }
}